#include <stdio.h>

/* 算法16-7：计算 a^i mod n的幂取模算法 PowMod(a, i, n) */
int PowMod(int a, int i, int n) {
    int x, y;

    if (i == 0) {
        return 1; /* a^0 mod n = 1 */
    }
    x = PowMod(a, i >> 1, n); /* 计算 a^{i/2} mod n */
    if (x == 0) {
        return 0; /* 若x为0，则n非素数，退出递归 */
    }
    y = (x * x) % n; /* 计算 (a^{i/2} mod n)*(a^{i/2} mod n) mod n */
    if (y == 1 && x != 1 && x != (n - 1)) { /* 违反二次探测定理，退出 */
        return 0;
    }
    if (i % 2 == 1) { /* 若i为奇数，再多乘一次a */
        y = (y * a) % n;
    }
    return y;
}
/* 算法16-7 结束 */

int main(void) {
    int a, i, n;

    scanf("%d %d %d", &a, &i, &n);
    printf("%d", PowMod(a, i, n));

    return 0;
}